package cn.cxq.learning.sort;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 数组中的逆序对
 * 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 64M，其他语言128M 热度指数：655227
 * 本题知识点： 数组
 *  算法知识视频讲解
 * 题目描述
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
 *
 * 对于50\%50%的数据,size\leq 10^4size≤10
 * 4
 *
 * 对于75\%75%的数据,size\leq 10^5size≤10
 * 5
 *
 * 对于100\%100%的数据,size\leq 2*10^5size≤2∗10
 * 5
 *
 * 输入描述:
 * 题目保证输入的数组中没有的相同的数字
 * 示例1
 * 输入
 * 复制
 * [1,2,3,4,5,6,7,0]
 * 返回值
 * 复制
 * 7
 */
public class InversePairs {

    int count = 0;

    @Test
    public void test() {
        System.out.println(InversePairs(new int[]{1, 2, 3, 4, 5, 6, 7, 0}));
    }

    // 看了题解之后发现归并大法好！
    public int InversePairs(int[] array) {

        int[] temp = new int[array.length];

        sort(array, 0, array.length - 1, temp);

        return count;
    }

    private void sort(int[] array, int left, int right, int[] temp) {

        int mid = (left + right) / 2;

        if (left < right) {
            sort(array, left, mid, temp);
            sort(array, mid + 1, right, temp);
            merge(array, left, mid, right, temp);
        }
    }

    private void merge(int[] array, int left, int mid, int right, int[] temp) {

        int i = left;
        int j = mid + 1;

        int index = left;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[index++] = array[i++];
            } else {
                temp[index++] = array[j++];
                count = (count + mid - i + 1) % 1000000007;
            }
        }

        while (i <= mid) {
            temp[index++] = array[i++];
        }

        while (j <= right) {
            temp[index++] = array[j++];
        }

        while (left <= right) {
            array[left] = temp[left++];
        }
    }

    // 超时
//    public int InversePairs(int[] array) {
//        int p = 0;
//        for (int i = array.length - 1; i >= 1; i--) {
//            for (int j = 0; j < i; j++) {
//                if (array[i] < array[j]) {
//                    p++;
//                }
//            }
//        }
//        return p % 1000000007;
//    }
}
